package LeetCode;

import java.util.LinkedList;
import java.util.List;

public class LC_068_TextJustification {
    public static void main(String[] args) {

    }

    static class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            List<String> res = new LinkedList<>();
            List<String> tmpList = new LinkedList<>();

            int length = words.length;
            int count = 0;

            for (int i = 0; i < length; i++) {
                count += words[i].length() + 1;
                tmpList.add(words[i]);

                if (i + 1 < length && count + words[i + 1].length() > maxWidth) {
                    int neededSpace = maxWidth - count + 1;
                    int size = tmpList.size();
                    int average, extra;

                    if (size == 1) {
                        average = neededSpace;
                        extra = 0;
                    } else {
                        average = neededSpace / (size - 1);
                        extra = neededSpace % (size - 1);
                    }

                    StringBuilder spaceStr = new StringBuilder();
                    for (int j = 0; j < average; j++)
                        spaceStr.append(' ');

                    StringBuilder builder = new StringBuilder();

                    while (!tmpList.isEmpty()) {
                        String tmp = tmpList.get(0);
                        tmpList.remove(0);
                        builder.append(tmp);
                        if (tmpList.isEmpty())
                            break;
                        builder.append(' ');
                        builder.append(spaceStr);
                        if (extra > 0) {
                            builder.append(' ');
                            extra--;
                        }
                    }
                    while (builder.length() < maxWidth)
                        builder.append(' ');

                    res.add(new String(builder));
                    count = 0;
                }
            }
            StringBuilder sb = new StringBuilder();
            while (!tmpList.isEmpty()) {
                sb.append(tmpList.get(0));
                tmpList.remove(0);
                sb.append(' ');
            }

            while (sb.length() < maxWidth)
                sb.append(' ');

            if (sb.length() > maxWidth)
                sb.deleteCharAt(maxWidth);

            res.add(sb.toString());
            return res;
        }
    }
}
